// 动态规划

var maxSubArray = function(nums) {
  let ans = nums[0];
  const dp = new Array(nums.length).fill(0);

  for (let i = 0; i < nums.length; i++) {
    dp[i] = nums[i]; 
  }

  for (let i = 1; i< nums.length; i++) {
    dp[i] = Math.max(dp[i - 1] + nums[i], dp[i]);
    ans = Math.max(dp[i], ans);
  }

  return ans;
}

const nums = [-2,1,-3,4,-1,2,1,-5,4];
console.log(maxSubArray(nums))